import java.util.Arrays;

public class Sort {

    public static void bubbleSort(int[] arr) {
        bubbleSort(arr, 0, arr.length - 1);
    }
    public static void bubbleSort(int[] arr, int left, int right) {
        for (int i = 0; i < right - left; i++) {// 外层循环是决定次数
            for (int j = left; j < right - i; j++) {// 内层循环决定范围
                if(arr[j] > arr[j + 1]) swap(arr, j, j + 1);
            }
        }
    }
    public static void heapSort(int[] arr) {
        heapSort(arr, 0, arr.length - 1);
    }
    public static void heapSort(int[] arr, int left, int right) {
        for (int end = right; end >= 0; end--) {
            swap(arr, 0, end);
            siftDown(arr, left, end - 1);
        }
    }

    public static void createBigHeap(int[] arr) {
        createBigHeap(arr, 0, arr.length - 1);
    }

    public static void createBigHeap(int[] arr, int left, int right) {
        int[] tmp = Arrays.copyOfRange(arr, left, right + 1);
        for (int parent = (tmp.length - 1 - 1) / 2; parent >= 0; parent--) {
            siftDown(tmp, parent, tmp.length - 1);
        }
        coverArray(arr, left, tmp, tmp.length);
    }

    private static void siftDown(int[] arr, int parent, int right) {
        int child = parent * 2 + 1;
        while(child <= right) {

            if(child + 1 <= right && arr[child] <= arr[child + 1]) child++;
            if(arr[child] > arr[parent]) {
                swap(arr, child, parent);
                parent = child;
                child = parent * 2 + 1;
            } else break;
        }
    }

    public static void selectSort(int[] arr) {
        selectSort(arr, 0, arr.length - 1);
    }
    public static void selectSort(int[] arr, int left, int right) {
        while(left < right) {
            int indexMax = left, indexMin = right;
            for (int i = left; i <= right; i++) {
                if(arr[indexMax] < arr[i]) indexMax = i;
                else if(arr[indexMin] > arr[i]) indexMin = i;
            }
            swap(arr, indexMin, left++);
            if(left - 1 == indexMax && right == indexMin) continue;
            swap(arr, indexMax, right--);
        }
    }
    public static void shellSort(int[] arr) {
        shellSort(arr, 0, arr.length - 1);
    }
    public static void shellSort(int[] arr, int left, int right) {
        int gap = right + 1;
        int[] tmp = Arrays.copyOfRange(arr, left, right + 1);
        createBigHeap(tmp);
        while(gap / 2 >= 1) {
            gap = gap / 2;
            shell(tmp, gap);
        }
        coverArray(arr, left, tmp, tmp.length);
    }
    private static void coverArray(int[] desc, int start, int[] src, int size) {
        for (int i = start; i < start + size; i++) {
            desc[i] = src[i - start];
        }
    }
    private static void shell(int[] arr,int gap) {
        insertSort(arr, 0, arr.length - 1, gap);
    }
    public static void insertSort(int[] arr) {
        insertSort(arr, 0, arr.length - 1, 1);
    }
    public static void insertSort(int[] arr, int left, int right) {
        insertSort(arr, left, right, 1);
    }
    private static void insertSort(int[] arr, int left, int right, int gap) {
        int tmp;
        for (int i = left + 1; i <= right; i++) {
            tmp = arr[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if(arr[j] > tmp) arr[j + gap] = arr[j];
                else break;
            }
            arr[j + gap] = tmp;
        }
    }
    public static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    /**
     *  ！！！ 由 partitionHoare 和 partitionHoare2 可以得出 ！！！
     *      结论：
     *          先从左边还是先从右边 与 起始值的位置（left/right）有关
     *              --> 据观察都是在对立面 意思就是 如果起始位置在 left 那么就要从右边开始寻找
     *          在左边取得较小值 还是取较大值 取决于是业务要求是降序还是升序
     *      解释：（以升序为例）
     *          如果是升序（目标左小右大） 那么左边原先是较大 右边原先就是较小
     *          在升序的基础上 右边的目标就是找到比较大的 左边的目标就是找到比较小的
     *          所以在排完后 除了起始位置 其余的基本就满足左小右大的关系（例如 5 2 3 8 7 或者 2 3 8 7 5）
     *          由此可得 如果起始位置在左边（原先比较大）那么就要找到较小值进行交换 所以要从右边开始 反之亦然
     */
    public static void quickSort(int[] arr, int left, int right) {
        if(left >= right) return;
//        int pivot = partitionHoare(arr, left, right);
        int pivot = partitionHole(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }
    // 降序
    private static int partitionHole(int[] arr, int left, int right) {
        int tmp = arr[left]; // 起始位置
        while(left < right) {

            while(left < right && arr[right] <= tmp) {
                right--; // 右边开始比较
            }
            arr[left] = arr[right];
            while(left < right && arr[left] >= tmp) {
                left++;
            }
            arr[right] = arr[left];
        }
        arr[left] = tmp;
        return left;
    }


    // 3. 需要升序 所以原来的可以看为 ‘左大又小’
    private static int partitionHoare(int[] arr, int left, int right) {
        int head = left; // 存储 '较小值' 只要要换位置就是较大的 1.
        while(left < right) {

            // 找比较小的
            while(left < right && arr[head] <= arr[right]) {
                right--;
            }
            // 找比较大的
            while(left < right && arr[left] <= arr[head]) {
                left++;
            }
            swap(arr, left, right);
        }
        // 最终 left 下面是要存储较大的 2.
        swap(arr, head, left);
        return left;
    }

    //降序
    private static int partitionHoare2(int[] arr, int left, int right) {
        int end = right; // 存储 '较大值' 只要要换位置就是较小的 1.
        while(left < right) {
            // 找比较小的
            while(left < right && arr[left] >= arr[end]) {
                left++;
            }

            // 找比较大的
            while(left < right && arr[end] >= arr[right]) {
                right--;
            }
            swap(arr, left, right);
        }
        // 最终 left 下面是要存储较小的 2.
        swap(arr, end, left);
        return left;
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }
    public static void mergeSort(int[] arr,int left,int right) {
        if(left >= right) return;
        int mid = (right - left) / 2 + left;
        // 分
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        // 排
        merge(arr, left, mid, right);
    }
    private static void merge(int[] arr, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1];
        int s1 = left, s2 = mid + 1, index = 0;
        while(s1 <= mid && s2 <= right) {
            if(arr[s1] < arr[s2]) {
                tmp[index++] = arr[s1++];
            } else {
                tmp[index++] = arr[s2++];
            }
        }
        while(s1 <= mid) {
            tmp[index++] = arr[s1++];
        }
        while(s2 <= right) {
            tmp[index++] = arr[s2++];
        }
        index = 0;
        for (int i = left; i <= right; i++) {
            arr[i] = tmp[index++];
        }
    }
}
